package code;

import java.util.ArrayList;
import java.util.List;

public class Code74 {
	
	/*
	 * 映射成一维的有序数组
	 */
	public boolean binarySearch(int[][] matrix,int target){
		int n=matrix.length;
		int m=matrix[0].length;
		int l=0,r=n*m-1;
		int ans=-1;
		int mid;
		while(l<r){
			mid=l+r>>1;
			int x=mid/m;
			int y=mid%m;
			if(matrix[x][y]==target)
				return true;
			if(matrix[x][y]>target)
				r=mid-1;
			else l=mid+1;
		}
		if(matrix[l/m][l%m]==target)
			return true;
		return false;
	}
	
    public boolean searchMatrix(int[][] matrix, int target) {
    	if(matrix.length==0)
    		return false;
    	
        return binarySearch(matrix,target);
    }
    
    public String addBinary(String a, String b) {
        if(a.length()==0)
        	return b;
        if(b.length()==0)
        	return a;
        int i;
        StringBuilder sb=new StringBuilder();
        int n=a.length()>b.length()?b.length():a.length();
        StringBuilder c=new StringBuilder();
        StringBuilder d=new StringBuilder();
        for(i=a.length()-1;i>=0;i--){
        	c.append(a.charAt(i));
        }
        for(i=b.length()-1;i>=0;i--){
        	d.append(b.charAt(i));
        }
        int add=0;
        for(i=0;i<n;i++){
        	int x=add;
        	if(c.charAt(i)=='1')
        		x++;
        	if(d.charAt(i)=='1')
        		x++;
        	if(x>=2){
        		x-=2;
        		add=1;
        	}
        	else add=0;
        	sb.append(x);
        }
        if(n==c.length() && n<d.length()){
        	for(i=n;i<d.length();i++){
        		int x=add;
        		if(d.charAt(i)=='1')
        			x++;
        		if(x>=2){
        			x-=2;
        			add=1;
        		}
        		else	
        			add=0;
        		sb.append(x);
        	}
        }
        else if(n==d.length() && n<c.length()){
        	for(i=n;i<c.length();i++){
        		int x=add;
        		if(c.charAt(i)=='1')
        			x++;
        		if(x>=2){
        			x-=2;
        			add=1;
        		}
        		else	
        			add=0;
        		sb.append(x);
        	}
        }
    	if(add==1){
    		sb.append(add);
    	}
    	StringBuilder ans=new StringBuilder();
    	for(i=0;i<sb.length();i++){
    		ans.append(sb.charAt(sb.length()-1-i));
    	}
        return ans.toString();
    }
    public int[] plusOne(int[] digits) {
    	List<Integer> list=new ArrayList<Integer>();
    	int n=digits.length;
    	int i;
    	int add=1;
    	for(i=n-1;i>=0;i--){
    		int x=add+digits[i];
    		if(x>9){
    			x-=10;
    			add=1;
    		}
    		else add=0;
    		list.add(x);
    	}
    	if(add==1){
    		list.add(1);
    	}
    	n=list.size();
    	int[] ans=new int[n];
    	for(i=0;i<n;i++){
    		ans[n-i-1]=list.get(i);
    	}
    	return ans;
    }
    
    public static void main(String[] args){
    	int[][] matrix={{1,3,5,7},{10,11,16,20},{23,30,34,50}};
//    	System.out.println(new Code74().binarySearch(matrix,3));
//    	System.out.println(new Code74().addBinary("11", "1"));
    	int[] digits={1,9};
    	System.out.println(new Code74().plusOne(digits));
    }
}
